package uestc.lj.basic.sort;

import java.util.PriorityQueue;

/**
 * 使用小根堆来对几乎有序的数组排序
 * 几乎有序意味着每个元素排好序之后的位置和原位置之差不超过k
 *
 * @Author:Crazlee
 * @Date:2021/11/21
 */
public class Code03_ArrayDistantLessKByHeapSort {
    /**
     * 排序几乎有序的数组
     *
     * @param array 待排数组
     * @param k     距离
     */
    public static void sortedArrayDistantLessK(int[] array, int k) {
        //使用小根堆即优先级队列(默认是小根堆)
        PriorityQueue<Integer> heap = new PriorityQueue<>();
        int index = 0;
        //将前k个数放入优先队列中
        for (; index < Math.min(array.length, k); index++) {
            heap.add(array[index]);
        }
        int i = 0;
        for (; index < array.length; i++, index++) {
            heap.add(array[index]);
            array[i] = heap.poll();
        }
        while (!heap.isEmpty()) {
            array[i++] = heap.poll();
        }
    }
}
